package com.example.algorithm.sorts;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 5, 9, 9, 9, 9};
        System.out.println(binarySearch(nums, 9, 0, 7));

    }

    /**
     *
     * @param arr
     * @param target
     * @param start
     * @param end
     * @return
     */
    public static int binarySearch(int[] arr, int target, int start, int end) {
        // 当二分到最后没有元素了，说明不存在
        if (end < start || arr[start] > target || arr[end] < target)
            return -1;

        int mid = (start + end) / 2;
        if (arr[mid] == target)
            return mid;

        if (arr[mid] > target) {
            return binarySearch(arr, target, start, mid -1);
        } else {
            return binarySearch(arr,target, mid + 1, end);
        }
    }
}
